A database is a collection of tables. These tables are arrays of information, where each row in the array constitutes a group of related data. For example, in an exemplary table representing bibliographic information, a first column includes author information and a second column includes title information. Other columns may also be included. Each row includes author, title, and publication date information, for example.
A table in a database may grow to be very large. If this occurs, storage and access may be difficult. A table in a database may be partitioned in order to provide more flexible storage or faster location of a row. Queries and statements on the database do not need to be modified in order to access partitioned tables, though partitions can be accessed and used separately as well. Partitions will be of a smaller size than the original table, and therefore partitioning simplifies the manageability of large database objects.
When a table is partitioned, the partitioning is done with a partition function. A key, related to the information in one or more columns of a row, is used as the input to the function. The output of the function is used to determine the partition in which the row should be found. Where there are N partitions, the partition function is a way to take the key for the row, and determine which partition (of partitions 1 through N) the row belongs in, based on the key.
For example, for a table with bibliographic information, the partition function may divide the rows into groups. In one example, the key may be the entry in the author's name column. Where there are 5 partitions, the partition function may place rows where the author's name begins with A through E in partition 1, F through I in partition 2, J through N in partition 3, O through S in partition 4, and T through Z in partition 5. Because this partition function breaks key values into ranges, this is known as range partitioning.
Where a hash function is used as the partition function, hash partitioning is achieved. Hash partitioning enables easy partitioning of data that does not lend itself to range partitioning. It is useful, for example, when it is not clear how much data will map into a given range or where range partitioning causes undesirable clustering. A hash function allows a mapping from the set of keys (for example, author's names) to the set of partitions (1 through N) with approximately equal distribution of partition assignments. The hash function is used to determine the partition for a given key, and in this way, the entry is assigned a partition. The resulting roughly equal distribution of entries over the partitions, so that approximately 1/N of the entries in each of N partitions, is desirable, in order to maximize the usefulness of partitioning the table.
In addition to a roughly equal distribution, when performing a partition, there are several other desirable characteristics of the partitioning. First, collocation is desirable. Where two tables T1 and T2 are partitioned, these tables are collocated if they have the same number of partitions and if there exists one-to-one correspondence between the partitions of T1 and T2. That is, if there are two rows, R1 in T1 and R2 in T2, and both R1 and R2 have the same key, then if R1 is in the Mth partition of T1, R2 should be in the Mth partition of T2. This allows efficiencies in searching. For example, T1 may be the bibliographic table mentioned above, with author, title and publishing date. T2 may be a list of author contact information, with author's name and author address. If T1 and T2 are both partitioned on the author's name and are collocated, then a search to find all authors listed in T1 and T2 will need to compare the entries in partition 1 of T1 with those in partition 1 of T2, the entries in partition 2 of T1 with those in partition 2 of T2, etc. Where there are N partitions, N pairs of partitions need to be searched. However, if T1 and T2 are not collocated, the entries in partition 1 of T1 would have to be compared with the entries in all partitions of T2, the entries in partition 2 of T1 would have to be compared with the entries in all partitions of T2, etc. Thus N2 pairs of partitions need to be searched. Thus, collocation reduces the necessary matching. As the number of partitions increases, this benefit is magnified.
As another example, two tables exist with employee data, with the first table including entries including an employee ID and an employee name, and the second table including the employee ID and an employer name, and it is desired to find the name of an employer for a given named employee. The tables are partitioned on employee ID. First, all the partitions in the first table would need be searched to find the employee name. This is because the partition is based on employee ID, not employee name. When the correct name is found, the employee ID can be used to look in the second table for the employer's name. If the first and second tables are collocated, and the employee's name was found in partition M of the first table, then the hash of the employee ID need not be performed. If an entry exists in the second table for that employee ID, it will be contained in partition M of the second table. Thus, a savings in calculating the hash of the key is realized.
An additional desirable characteristic of partitioning is minimal data movement when adding and removing partitions. For example, a hash to four buckets may be used to spread a table across 4 partitions. This may be done in order to use four available storage devices. If an additional storage device is obtained, it may be desirable to implement 5 partitions. This may be done with a new hash function. It is desirable to create a new partition in such a way that an entry either remains in its original partition in the 4-partition or moves to the new partition. In this way, there will be minimal movement necessary to implement the new partition—only the entries being switched from their old partition to the newly created partition need to move. If there is roughly uniform distribution between the partitions, this means that adding a new partition will bring the total number of partitions to N, only approximately 1/N of the entries need to be moved in order to implement the new partition. The minimal amount of data should be moved to have an approximately even distribution even where more than one partition is being added. Similarly, if the new partitioning is to a smaller number of partitions, only entries in the eliminated partitions should be moved.
If, for example, the range partition described above with 5 partitions, where keys starting A through E are placed in partition 1, F through I in partition 2, J through N in partition 3, O through S in partition 4, and T through Z in partition 5 were repartitioned to 6 partitions, a new partition might be: A through D in partition 1, E through G in partition 2, H through L in partition 3, M through Q in partition 4, R through U in partition 5, and V through Z in partition 6. However, this likely moves more than ⅙ of the entries, since in addition to entries moving to partition 6, entries move from partition 1 to 2, from 2 to 3, from 3 to 4, etc. A range partition might be repartitioned with minimal movement, in our example, this might be done by a partition that moves entries starting with E, I, N, S, and Z to the new partition. However, this creates a more complex algorithm for determining partitions (which might become increasingly complex as partitions are added and deleted) and does not display another desirable characteristic of partitioning: associativity.
Associativity of hash partitioning is achieved when changes in the number of partitions does not change the resulting partition. For example, if a table is originally partitioned into Q partitions, and a new partitioning of the table into R partitions is made, the partition is associative if the new partitioning is the same partition that would have occurred if the table had originally partitioned into R partitions. This should be true whether Q>R or Q<R, in other words, whether one or more partitions have been added whether one or more partitions have been removed. If a partitioning is associative, then where two tables are partitioned on the same key into different numbers of partitions, repartitioning one table will produce a collocated partitioning. Thus processing advantages are realized.
While each of these desirable characteristics of collocation, minimal data movement, and associativity is individually present in prior art partitioning systems and methods, there is a need for a partitioning system and method which displays all of these characteristics. For example, as discussed above, a range repartition which produces minimal data movement is not associative. Similarly, no prior art hash function produces both minimal data movement and associativity.
Thus, there is a need for a method and system for hash partitioning with characteristics including collocation, minimal data movement, and associativity that overcomes the drawbacks in the prior art.